package Finding_Numbers_by_Dichotomy;

import java.util.Random;

//找局部最小
//前提数组为邻位不相等的数组
public class test2 {

    public static int Find_local_minimum(int[] arr) {
        int ans = -1;
        if (arr.length == 0 || arr == null) {
            return -1;
        } else if (arr.length == 2) {
            return arr[0] > arr[1] ? 1 : 0;
        } else if (arr.length == 1) {
            return 0;
        } else {
            int l = 0;
            int r = arr.length - 1;

            if (arr[0] < arr[1]) {
                return 0;
            } else if (arr[arr.length - 1] < arr[arr.length - 2]) {
                return arr.length - 1;
            } else {
                while (l < r ) {
                    int mid = (r + l) / 2;
                    if (arr[mid] < arr[mid + 1] && arr[mid] < arr[mid - 1]) {
                        return mid;
                    }
                    if (arr[mid] > arr[mid + 1]) {
                        l = mid;
                    } else {
                        r = mid;
                    }
                }
            }
        }
        return ans;
    }

    public static int[] randomArray(int maxvalue, int maxLen) {
        Random num = new Random();
        int len = num.nextInt(maxLen) + 1;
        int[] arr = new int[len];
        arr[0] = num.nextInt(maxvalue);
        for (int i = 1; i < len; i++) {
            do {
                arr[i] = num.nextInt(maxvalue) + 1;
            } while (arr[i] == arr[i - 1]);
        }
        return arr;
    }

    public static boolean check(int[] arr, int minIndex) {
        int left = minIndex - 1;
        int right = minIndex + 1;
        boolean leftBigger = left <= 0 || arr[left] > arr[minIndex];
        boolean rightBigger = right >= arr.length || arr[right] > arr[minIndex];
        return leftBigger && rightBigger;
    }




    public static void main(String[] args) {
        int count = 0;
        for (int i = 0; i < 1000000; i++) {
            int[] arr = randomArray(10,10);
            int a = Find_local_minimum(arr);
            if(a==-1){//a不可能出现-1
                count++;
            }
            if(!check(arr,a)) {
                System.out.println("出错了");
            }
        }
//        int[] arr = {3,2,3,2,3};
//        if(!check(arr,2)) {
//            System.out.println("出错了");
//        }
        System.out.println(count);
    }
}
